Fixed-point multiplication is a fundamental arithmetic operation performed by digital computational circuits, such as processors. Most processor instruction set architectures include a variety of fixed-point multiply instructions. A known hazard of fixed-point multiplication is that under some conditions (as more fully described herein), a product may exceed the numeric value that can be represented in the available bit width, a condition known as overflow. In this case, to avoid a gross misrepresentation of the product, a multiply instruction will specify a “saturated” output, which is the largest numerical value that can be represented in the available bit field—in effect, the closest approximation possible to the actual product. This is known as a saturating fixed-point multiply instruction. Such instructions typically specify a bit width for the product that is twice the bit width of the operands.
Both integer and fractional values can be represented in fixed-point digital form, depending on the convention used. Commonly all modern processors use the two's complement format to represent positive and negative integers in fixed-width digital representations. The two's complement format is common. In two's complement representation, integers are “signed.” That is, whether an integer is positive or negative may be determined by inspection of the Most Significant Bit (MSB), or the “sign bit.” Additionally, in two's complement representation, binary arithmetic operations on signed integers yield the correct two's complement results.
Positive two's complement numbers are represented in simple binary form, with a zero sign bit. Consequently, the largest positive number that can be represented in two's complement format is 2n-1−1, where n is the bit width of the digital representation. Negative two's complement numbers are represented as the binary number that when added to a positive number of the same magnitude equals zero. Negative two's complement numbers have a sign bit of one. Since the two's complement representation of negative numbers may utilize all n bits of the digital representation, the largest negative number that can be represented in two's complement format is 2n-1, which is one larger in magnitude than the largest positive two's complement number. Thus, for example, the range of signed integer values that may be represented in a 32-bit field is −231 (0×8000 0000) to +231−1 (0×7FFF FFFF).
The negation of any two's compliment number may be formed by bit-wise inverting the number (yielding the one's complement), and adding one. Hence, one way to calculate the two's complement representation of a negative number is to invert the binary representation of the corresponding positive number (which is the one's compliment form of that positive number) and add one. The sole exception to this algorithm for negation is the largest negative number than can be represented. Performing a two's compliment negation on that number results in the same number, which is an overflow error. Note also that negating the two's compliment of zero yields zero—inverting all the bits yields all ones, and adding one yields zero (when the carry out is discarded).
Fractional values may be represented in fixed-width digital form using the so-called Q format notation. In Qn.x format notation, the bits of a value are interpreted as: one sign bit, n integer bits and x fraction bits. A common Q format for digital signal processing is Q0.x (or simply Q.x) indicating that there is one sign bit, no integer bits and x fraction bits. A number in Q.31 notation would be expressed in 32 bits and would have values ranging from −1 (0×8000 0000) to 1-2−31 (o×7FFF FFFF).
When multiplying numbers in Q format, it is important to account for the binary point. For example, multiplying a Q.15 times a Q.15 will yield a result in Q2.30. However, it is desirable to keep the value in Q.x format. To handle this, the multiplication operations include a multiplication by a factor of 2—which is equivalent to a left shift operation—to produce a Q.31 result. Multiplying two n-bit values together will always produce a value that can be represented in 2n bits. Doubling this product will produce a value that can be represented in 2n bits in all but one case: the maximum negative value. The maximum negative value in two's complement is a sign bit (MSB) of one with all other bits zero. Shifting this value left results in an overflow.
An example is the following multiplication of two 16-bit operands to generate a 32-bit product. Each of the operands is negative (sign bit of one), and their product should be a positive number.                0×8000×0×8000=0×4000 0000 Multiplication        0×4000 0000×0×2=0×8000 0000 Doubling (incorrect result; should be positive)        0×8000 0000−1=0×7FFF FFFF Saturated Result (largest positive value)In this example, the two operands are each the largest negative number that can be represented in 16 bits in two's complement format. Their product should yield a large positive value. However, the actual result of the doubling multiply instruction is the largest negative value. Hence, a ‘1’ must be subtracted from this value to obtain the saturation value of 0×7FFFFFFF—a zero sign bit with all ones in the other bit positions.        
Conventional saturating multipliers detect an overflow condition only after the multiplication is performed, and must then take steps to correct the overflow condition by saturating the output. In some implementations, this may require halting the processor, such as by causing an exception. This adversely impacts processor performance and causes increased power consumption. Even where the overflow is saturated in hardware, doing so after the multiplication completes adversely impacts performance.